public class BinarySearch
{
    public static final int NOT_FOUND = -1;

    public static int iterBinarySearch( Comparable [ ] a, Comparable x )
    {
        int low = 0;
        int high = a.length - 1;
        int mid;

        while( low <= high )
        {
            mid = ( low + high ) / 2;

            if( a[ mid ].compareTo( x ) < 0 )
                low = mid + 1;
            else if( a[ mid ].compareTo( x ) > 0 )
                high = mid - 1;
            else
                return mid;
        }

        return NOT_FOUND;     // NOT_FOUND = -1
    }

    public static int recBinarySearch( Comparable [ ] a, Comparable x,
                                         int low, int high )
    {
        if (low > high)
            return NOT_FOUND;
        
        int mid = ( low + high ) / 2;
        
        if( a[ mid ].compareTo( x ) < 0 )
            return recBinarySearch( a, x, mid + 1, high );
        else if( a[ mid ].compareTo( x ) > 0 )
            return recBinarySearch( a, x, low, mid - 1 );
        else
            return mid;
    }

    // Test program
    public static void main( String [ ] args )
    {
        int SIZE = 8;
        Comparable [] a = new Integer [SIZE];
        
        for( int i=0; i < SIZE; i++) {
            a[i] = new Integer(i * 2);
        }

        System.out.println("Found 8 at " +
                             iterBinarySearch(a, new Integer(8)));
        System.out.println("Found 9 at " +
                             iterBinarySearch(a, new Integer(9)));

    }
}